package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder3
import java.util.*
import kotlin.collections.ArrayList

/**
 * https://leetcode.cn/problems/reverse-odd-levels-of-binary-tree/description
 *
 * ```
 * 2415. 反转二叉树的奇数层
 *
 * 给你一棵 完美 二叉树的根节点 root ，请你反转这棵树中每个 奇数 层的节点值。
 * 例如，假设第 3 层的节点值是 [2,1,3,4,7,11,29,18] ，那么反转后它应该变成 [18,29,11,7,4,3,1,2] 。
 * 反转后，返回树的根节点。
 * 完美 二叉树需满足：二叉树的所有父节点都有两个子节点，且所有叶子节点都在同一层。
 * 节点的 层数 等于该节点到根节点之间的边数。
 *
 * 示例 1：
 * 输入：root = [2,3,5,8,13,21,34]
 * 输出：[2,5,3,8,13,21,34]
 * 解释：
 * 这棵树只有一个奇数层。
 * 在第 1 层的节点分别是 3、5 ，反转后为 5、3 。
 *
 * 示例 2：
 * 输入：root = [7,13,11]
 * 输出：[7,11,13]
 * 解释：
 * 在第 1 层的节点分别是 13、11 ，反转后为 11、13 。
 *
 * 示例 3：
 * 输入：root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
 * 输出：[0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
 * 解释：奇数层由非零值组成。
 * 在第 1 层的节点分别是 1、2 ，反转后为 2、1 。
 * 在第 3 层的节点分别是 1、1、1、1、2、2、2、2 ，反转后为 2、2、2、2、1、1、1、1 。
 *
 * 提示：
 * 树中的节点数目在范围 [1, 214] 内
 * 0 <= Node.val <= 105
 * root 是一棵 完美 二叉树
 * ```
 */
class leetcode_2415 {
    @Test
    fun test_3() {
        val n7 = TreeNode(7)
        val n13 = TreeNode(13)
        val n11 = TreeNode(11)
        val root = n7
        n7.left = n13
        n7.right = n11
        val actual = reverseOddLevels(root)
        val expect = arrayListOf(7, 11, 13)
        Assert.assertEquals(expect, printLevelOrder3(actual))
    }

    private fun reverseOddLevels(root: TreeNode?): TreeNode? {
        /**
        题型：二叉树的层级遍历，节点的层数与树的层数不同

        思路：
        题目要求是：反转每个奇数层的所有节点值，不是仅仅左右孩子交换值。
        遍历当前层时，当节点的层数是奇数时，收集节点和值。
        遍历当前层结束后，若节点的层数是奇数时，重新设置反转后的数值。然后更新层数。
         */
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if (null == root) {
            return null
        }
        // 3 确定单层递归的处理逻辑: 非递归，层级遍历
        var depth:Int = 0
        val list:ArrayList<TreeNode> = ArrayList()
        val items: ArrayList<Int> = ArrayList()

        val queue: LinkedList<TreeNode> = LinkedList()
        queue.offer(root)

        while(!queue.isEmpty()){
            depth++
            var size: Int = queue.size

            while(size -- > 0){
                val node = queue.poll()
                node.left?.let{
                    queue.offer(it)
                }
                node.right?.let{
                    queue.offer(it)
                }
                // 节点奇数层，等于 树的深度偶数层
                if(depth > 0 && depth % 2 == 0){
                    list.add(node)
                    items.add(node.`val`)
                }
            }

            if(items.size > 0){
//                println("before:${items}")
                items.reverse()
//                println("after:${items}")

                for(i in 0 until items.size){
                    list[i].`val` = items[i]
                }

                list.clear()
                items.clear()
            }
        }
        return root
    }
}